import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
import numpy as np

#Delaunay算法
def drawDelaunay(width,height,pointNumber):
    # Triangle Settings
    points = np.zeros((pointNumber,2))
    points[:,0] = np.random.randint(0, width, pointNumber)
    points[:,1]= np.random.randint(0, height, pointNumber)
    #print("%r"%points)
    # Use scipy.spatial. Delaunay for Triangulation
    tri = Delaunay(points)
    #print("%r" %tri.simplices)

    # Plot Delaunay triangle with color filled
    plt.figure(figsize=(7,3))
    for T in tri.simplices:
        Tp= points[T,:]
        x=Tp[:,0]
        y=Tp[:,1]
        plt.plot(x[[0,1]], y[[0,1]])
        plt.plot(x[[0,2]], y[[0,2]])
        plt.plot(x[[2,1]], y[[2,1]])
    plt.tick_params(labelbottom ='off', labelleft='off', left='off', right='off',
                        bottom ='off', top=' off')
    # Save picture
    plt.savefig('./ch_13/Delaunay.png',transparent=False, dpi=300)
    plt.show()
    return tri

def Delaunay2graph(tri):
    #tri=drawDelaunay(width,height,pointNumber)
    R=tri.simplices
    E=set({})
    for k in range(len(R)):
        [x,y,z]=list(R[k])
        E=E|{(x,y),(y,z),(z,x)}
    return E